// 1. 动态规划
// 定义：dp[n]表示1-n个数可以组成多少二叉排序树；F[i,n]表示以i为根节点，1-n个数可以组成多少二叉排序树；
// dp[n] = F[1,n] + F[2,n] + F[3,n] + ... + F[n,n]
// F[i,n]=dp[i-1]*dp[n-i]
// 举例说明，[1,2,3,...,n-1,n]，假定以i为根节点，左子树为[1,2,...,i-1]，右子树为[i+1,i+2,...,n-1,n]，左半边个数*右半边个数，那么F[i,n]=dp[i-1]*dp[n-i]
//所以，dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+...+dp[n-1]*dp[0]

//初始化：dp[0]=1, dp[1]=1!!!
//注意dp[0]=1, dp[1]肯定=1,反推dp[1]=dp[0]*dp[0],dp[0]=1
func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1

	for i := 2; i <= n; i++ {
		for j := 0; j <= i-1; j++ {
			dp[i] += dp[j] * dp[i-j-1]
		}
	}

	return dp[n]
}